package com.atwulidun.avltree;

import java.util.Scanner;

public class AVLTreeDemo {
    public static void main(String[] args) {
        // 测试添加
        avlAddTest();
        // 测试删除
//        avlDeleteTest();
    }

    public static void avlAddTest() {
        AVLTree avlTree = new AVLTree();
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("请输入你要添加的结点：");
            int key = scanner.nextInt();
            System.out.println();
            avlTree.add(new Node(key));
            TreeOperation.show(avlTree.getRoot());
        }
    }

    public static void avlDeleteTest() {
        AVLTree avlTree = new AVLTree();
        for (int i = 0; i < 10; i++) {
            avlTree.add(new Node(i + 1));
        }
        TreeOperation.show(avlTree.getRoot());
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("请输入你要删除的结点:");
            int key = scanner.nextInt();
            System.out.println();
            avlTree.del(key);
            TreeOperation.show(avlTree.getRoot());
        }
    }
}

class AVLTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    // 添加结点的方法
    public void add(Node node) {
        // 如果root为空，则把添加的结点作为root结点
        if (root == null) {
            root = node;
        } else {
            root.avlAdd(node);
        }
    }

    // 查找要删除结点的方法
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉排序树为空，不能遍历！");
        } else {
            root.infixOrder();
        }
    }

    // 查找要删除结点的父结点的方法
    // 中序遍历的方法
    // 删除结点的方法，分为三种情况：
    // 1.待删除结点为叶子结点(父结点是否根结点)
    // 2.待删除结点有左右两个子树
    // 3.待删除结点只有左子树或者右子树(父结点是否根结点)
    public void del(int value) {
        if (root == null) {
            System.out.println("二叉排序树为空，不能删除！");
            return;
        }
        if (root.search(value) == null) {
            System.out.println("要删除的结点不存在！");
            return;
        }
        root = root.avlDelete(value);
    }

    // 以下为AVL树对应的方法
    // 如果求最大深度的方法不写在Node中
    // 把根结点传进来即可
    public int getMaxDepth(Node node) {
        if (node == null) {
            return 0;
        }
        return Math.max(getMaxDepth(node.getLeft()), getMaxDepth(node.getRight())) + 1;
    }

    // 如果求最小深度的方法不写在Node中
    // 把根结点传进来即可
    public int getMinDepth(Node node) {
        if (node == null) {
            return 0;
        }
        // 还要加额外的判断
        // 如果当前结点左子结点为null，则就求以当前结点右子结点为根结点的二叉树的最小深度再加上当前结点的高度
        if (node.getLeft() == null) {
            return getMinDepth(node.getRight()) + 1;
        }
        // 如果当前结点右子结点为null，则就求以当前结点左子结点为根结点的二叉树的最小深度再加上当前结点的高度
        if (node.getRight() == null) {
            return getMinDepth(node.getLeft()) + 1;
        }
        // 当当前结点的左右子结点都不为空时
        return Math.min(getMinDepth(node.getLeft()), getMinDepth(node.getRight())) + 1;
    }

    // 传进来一个有序数组，以其生成一棵AVL树
    public Node createAVLTree(int[] arr, int left, int right) {
        if (left > right) {
            return null;
        }
        // 先找到中间数作为根结点
        int mid = left + (right - left) / 2;
        Node root = new Node(arr[mid]);
        // 创建左结点
        root.setLeft(createAVLTree(arr, left, mid - 1));
        // 创建右结点
        root.setRight(createAVLTree(arr, mid + 1, right));
        return root;
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;


    public Node(int value) {
        this.value = value;
    }

    // 查找要删除结点的方法
    // 分为三种情况进行讨论
    public Node search(int value) {
        // 如果要查找的值等于当前结点的值，直接返回当前结点
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            // 如果要查找的值小于当前结点的值
            // 如果当前结点的左结点为空，说明不存在要查找结点
            if (this.left == null) {
                return null;
            } else {
                // 如果当前结点的左结点不为空，则递归查找
                return left.search(value);
            }
        } else {
            // 如果要查找的值大于当前结点的值
            // 如果当前结点的右结点为空，说明要查找的结点不存在
            if (this.right == null) {
                return null;
            } else {
                // 如果当前结点的右结点不为空，则递归查找
                return right.search(value);
            }
        }
    }

    // 查找要删除结点的父结点的方法
    public Node searchParent(int value) {
        // 若当前结点的左结点或右结点的值等于要查找的值，那么直接返回当前结点即可
        if (left != null && left.value == value || right != null && right.value == value) {
            return this;
        }
        // 若要查找的值小于当前结点的值，则左递归查找
        if (value < this.value && left != null) {
            return left.searchParent(value);
        } else if (value >= this.value && right != null) {
            // 若要查找的值大于等于当前结点的值，则右递归查找
            return right.searchParent(value);
        } else {
            // 最后一种就是找不到的情况
            return null;
        }
    }

    // 中序遍历的方法
    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    // 以下为AVL树对应的方法
    // 获取以当前结点为根结点的二叉树的最大深度
    public int height() {
        // 如果左子树为null，则左子树的高度为0；如果右子树为null，右子树的高度为0
        // 如果左子树不为null，递归获取左子树的最大深度；如果右子树不为null，递归获取右子树的最大深度
        // 获取左右子树最大深度的最大值，最后的+1即为加上当前结点的高度
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    // 获取当前结点左子树的最大深度
    public int leftHeight() {
        // 如果左子树为null，直接返回0即可
        if (left == null) {
            return 0;
        } else {
            // 如果不为null，以当前左结点为根结点获取左子树的最大深度
            return left.height();
        }
    }

    // 获取当前结点右子树的最大深度
    public int rightHeight() {
        // 如果右子树为null，直接返回0即可
        if (right == null) {
            return 0;
        } else {
            // 如果不为null，以当前右结点为根结点获取右子树的最大深度
            return right.height();
        }
    }

    // 获取以当前结点为根结点的二叉树的最小深度
    // 分为四种情况进行讨论
    public int minDepth() {
        if (left == null && right == null) {
            return 1;
        } else if (left != null && right == null) {
            return left.minDepth() + 1;
        } else if (left == null && right != null) {
            return right.minDepth() + 1;
        } else {
            return Math.min(left.minDepth(), right.minDepth()) + 1;
        }
    }

    // 左旋转(rightHeight - leftHeight > 1)
    public void leftRotate() {
        // 1,以当前结点的value新建一个结点
        Node newNode = new Node(value);
        // 2.新结点的左指针指向当前结点的左结点
        newNode.left = left;
        // 3.新结点的右指针指向当前结点右结点的左结点
        newNode.right = right.left;
        // 4.将当前结点右结点的值赋给当前结点
        value = right.value;
        // 5.当前结点的右指针指向当前结点右结点的右结点
        right = right.right;
        // 6.当前结点的左指针指向新结点
        left = newNode;
    }

    // 右旋转(leftHeight - rightHeight > 1)
    public void rightRotate() {
        // 1.以当前结点的值创建一个新结点
        Node newNode = new Node(value);
        // 2.新结点的右指针指向当前结点的右结点
        newNode.right = right;
        // 3.新结点的左指针指向当前结点左结点的右结点
        newNode.left = left.right;
        // 4.将当前结点的左结点的值赋值给当前结点
        value = left.value;
        // 5.当前结点的左指针指向当前结点左结点的左结点
        left = left.left;
        // 6.当前结点的右指针指向新结点
        right = newNode;
    }

    // 如果待删除结点的左右子结点都不为空，则需要找到其左子树中的最大值或其右子树中的最小值
    // 找待删除结点右子树中的最小值对应的结点，把最小值缓存下来后将该结点删掉，把待删除结点的值赋为缓存的值
    public int getRightTreeMin(Node node) {
        Node temp = node;
        while (temp.getLeft() != null) {
            temp = temp.getLeft();
        }
        // 找到最小值后返回
        return temp.getValue();
    }

    // 找待删除结点左子树中的最大值对应的结点，把最大值缓存下来后将该结点删掉，把待删除结点的值赋为缓存的值
    public int getLeftTreeMax(Node node) {
        Node temp = node;
        while (temp.getRight() != null) {
            temp = temp.getRight();
        }
        // 找到最大值后返回
        return temp.getValue();
    }

    // 利用avl原理来添加结点的方法
    // 当添加完一个结点后，要对二叉树的结构进行调整，使其成为一棵avl树
    // 注意：这里是递归调整，层层向上调整！！！！！！！！！！！
    public void avlAdd(Node node) {
        // 如果node为空，直接返回
        if (node == null) {
            return;
        }
        // 判断新结点要加在当前结点的左边还是右边
        // 如果要添加的结点的值小于当前结点的值
        if (node.value < value) {
            // 如果当前结点的左结点为空，直接添加
            if (this.left == null) {
                this.left = node;
            } else {
                // 如果当前结点的左结点不为空，则递归添加
                left.avlAdd(node);
            }
            // 左边添加了结点，可能会导致不平衡，需要进行调整
            // 进行右旋转
            if (leftHeight() - rightHeight() > 1) {
                // 如果当前结点的左结点不为空，以该左结点为根结点的右子树的高度大于其左子树的高度，则先以该左结点为根结点进行左旋转，然后再对当前结点进行右旋转
                if (left != null && left.rightHeight() > left.leftHeight()) {
                    left.leftRotate();
                }
                // 如果上面的条件不满足，则直接对当前结点进行右旋转即可
                rightRotate();
            }
        } else {
            // 如果要添加结点的值大于等于当前结点的值
            // 如果当前结点的右结点为空，直接添加
            if (this.right == null) {
                this.right = node;
            } else {
                // 如果当前结点的右结点不为空，则递归添加
                right.avlAdd(node);
            }
            // 右边添加了结点，可能导致不平衡，需要进行调整
            // 进行左旋转
            if (rightHeight() - leftHeight() > 1) {
                // 如果当前结点的右结点不为空，以该右结点为根结点的左子树的高度大于其右子树的高度，则先以该右结点为根结点进行右旋转，然后再对当前结点进行左旋转
                if (right != null && right.leftHeight() > right.rightHeight()) {
                    right.rightRotate();
                }
                // 如果上面的条件不满足，则直接对当前结点进行左旋转即可
                leftRotate();
            }
        }
    }

    // 删除结点的方法(这里是把查找和删除整合在一起了)
    // 删除一个结点，要层层向上递归进行调整
    // 对该方法进行调用，前提必须是value的值是存在的
    public Node avlDelete(int value) {
        // 要删除的结点是当前结点，那么分两种情况进行讨论：
        // 当前结点有两个子结点；当前结点只有一个子结点或者没有子结点
        if (value == this.value) {
            // 情况一：若当前结点有两个子结点
            if (left != null && right != null) {
                // 若当前结点的左子树比右子树高，则从左子树找一个最大的结点来替代当前结点，这样可以保持平衡
                if (leftHeight() > rightHeight()) {
                    // 从左子树找一个最大值
                    int max = getLeftTreeMax(left);
                    // 将该最大值赋给当前结点
                    this.value = max;
                    // 将找到的有最大值的该左子树结点删除
                    // 要用left对avlDelete方法进行调用，因为在递归中会对左子树进行调整
                    left = left.avlDelete(max);
                } else {
                    // 若当前结点的右子树比左子树高，则从右子树找一个最小的结点来替代当前结点，这样可以保持平衡
                    int min = getRightTreeMin(right);
                    // 将该最小值赋给当前结点
                    this.value = min;
                    // 将找到的有最小值的该右子树结点删除
                    // 要用right对avlDelete方法进行调用，因为在递归中对右子树进行调整
                    right = right.avlDelete(min);
                }
            } else {
                // 情况二：若当前结点只有一个子结点或者没有子结点，要找到当前结点被删除后的替代结点
                // replacement的值可能为left、right或null三种情况
                Node replacement = left != null ? left : right;
                // 直接返回替代结点即可
                return replacement;
            }
        } else if (value < this.value) {
            // 如果要删除的值小于当前结点的值，那么递归向左子树删除
            left = left.avlDelete(value);
            // 左子树删除结点后可能导致不平衡，需要进行调整
            // 进行左旋转
            if (rightHeight() - leftHeight() > 1) {
                // 如果当前结点的右结点不为空，以该右结点为根结点的左子树的高度大于其右子树的高度，则先以该右结点为根结点进行右旋转，然后再对当前结点进行左旋转
                if (right != null && right.leftHeight() > right.rightHeight()) {
                    right.rightRotate();
                }
                // 如果上面的条件不满足，则直接对当前结点进行左旋转即可
                leftRotate();
            }
        } else {
            // 如果要删除的值大于当前结点的值，那么递归向右子树删除
            right = right.avlDelete(value);
            // 右子树删除结点后可能导致不平衡，需要进行调整
            // 进行右旋转
            if (leftHeight() - rightHeight() > 1) {
                // 如果当前结点的左结点不为空，以该左结点为根结点的右子树的高度大于其左子树的高度，则先以该左结点为根结点进行左旋转，然后再对当前结点进行右旋转
                if (left != null && left.rightHeight() > left.leftHeight()) {
                    left.leftRotate();
                }
                // 如果上面的条件不满足，则直接对当前结点进行右旋转即可
                rightRotate();
            }
        }
        return this;
    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

class TreeOperation {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    // 用于获得树的层数
    public static int getTreeDepth(Node root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
    }


    private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }
    public static void show(Node root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}
